#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
	int getLeftDepth(TreeNode* node)
	{
		int depth = 0;
		while (node)
		{
			depth++;
			node = node->left;
		}
		return depth;
	}
	int getRightDepth(TreeNode* node)
	{
		int depth = 0;
		while (node)
		{
			depth++;
			node = node->right;
		}
		return depth;
	}
	int countNodes(TreeNode* root) {
		if (!root) return 0;
		int leftDeepth = getLeftDepth(root);
		int rightDeepth = getRightDepth(root);

		if (leftDeepth == rightDeepth)
		{
			return (1 << leftDeepth) - 1;
		}
		else
		{
			return 1 + countNodes(root->left) + countNodes(root->right);
		}
	}
};